package com;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class TSRandom {
	
	/*This method uses the random method algorithm to solve TS.*/
	
	static double compute(SimpleWeightedGraph<Node, DefaultWeightedEdge> graph) {
		 
		//Initialise minDist to zero.
		double minDist = 0.0;
		
		//Initialise 'weight' to zero.
		double weight = 0.0;
		
		//HashSet offers constant-time performance on the 'contains' operation, the only one we need.
		HashSet<Node> visitedNodes = new HashSet<Node>();
		
		//Get all nodes in the graph.
		Set<Node> vertices = graph.vertexSet();
		
		//Pick any vertex to start.
		Iterator<Node> iterN = vertices.iterator();
		Node activeNode = iterN.next();
		
		//A reference to the 1st node visited.
		Node firstNode = activeNode;
		
		//Iterate through the vertices.
		while (!(visitedNodes.size() >= vertices.size())) {
								
								//reset the 'next vertex' pointer.
								Node nextNode = null;
								
								//iterate through all the edges connected to the vertex until you find an unvisited node.
								Set<DefaultWeightedEdge> edgesFromNode = graph.edgesOf(activeNode);
								Iterator<DefaultWeightedEdge> iterE = edgesFromNode.iterator();
								while (iterE.hasNext()) {
										//get a random edge connected to the vertex.
										DefaultWeightedEdge edge = iterE.next();
										//find the target vertex of the edge.
										Node node = graph.getEdgeSource(edge);
										Node targetNode;
										if (node.equals(activeNode)) {targetNode = graph.getEdgeTarget(edge);}
										else {targetNode = node;}
										//get weight of the edge.
										weight = graph.getEdgeWeight(edge);
										//if the new vertex is unvisited, update 'next vertex' pointer and exit loop.
										if (!visitedNodes.contains(targetNode)) {
												nextNode = targetNode;
												break;
										}
										else {}
								}
								//mark the current vertex as 'visited'.
								visitedNodes.add(activeNode);								
								//test if we are at the last vertex. if we are, update minTime with edge from this 
								//vertex back to the 1st one. otherwise, update with weight of this edge.
								if (visitedNodes.size() < vertices.size()) {minDist += weight;}
								else {minDist += graph.getEdgeWeight(graph.getEdge(firstNode, activeNode));}
								//update the pointer to next vertex to be visited.
								activeNode = nextNode;
										
		}						
		
		return minDist;					
		
	}
}
